package java学习.leetcode.editor.cn.数组;

import java.util.Arrays;

/**
 * @author 刘世锦
 * 2022-09-26 17:12:31	 当前时间
 */
//给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。 
//
// 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-4,-1,0,3,10]
//输出：[0,1,9,16,100]
//解释：平方后，数组变为 [16,1,0,9,100]
//排序后，数组变为 [0,1,9,16,100] 
//
// 示例 2： 
//
// 
//输入：nums = [-7,-3,2,3,11]
//输出：[4,9,9,49,121]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 104 
// -104 <= nums[i] <= 104 
// nums 已按 非递减顺序 排序 
// 
//
// 
//
// 进阶： 
//
// 
// 请你设计时间复杂度为 O(n) 的算法解决本问题 
// 
// Related Topics 数组 双指针 排序 
// 👍 637 👎 0

public class 有序数组的平方{
	public static int in = 0;
	有序数组的平方(){
		System.out.println(in);
	}
	public static void main(String[] args) {
		for (int c = 0;;){
			System.out.println("1");
			break;
		}
		Solution solution = new 有序数组的平方().new Solution();
		int[] nums = {-4,-1,0,3,10};
		solution.sortedSquares(nums);
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {


    public int[] sortedSquares1(int[] nums) {
//输入：nums = [-4,-1,0,3,10]
//输出：[0,1,9,16,100]
//解释：平方后，数组变为 [16,1,0,9,100]
//排序后，数组变为 [0,1,9,16,100]
		for (int i = 0; i < nums.length; i++) {
			nums[i] *= nums[i];
		}
		Arrays.sort(nums);
//		System.out.println(Arrays.toString(nums));
		return nums;
    }

	public int[] sortedSquares(int[] nums) {
    	int i=0,j = nums.length-1;
    	int[] result = new int[nums.length];
//    	为什么index一定是从后往前：
//    		因为数组有序，故最大的元素定在两侧，最终结果也要保持有序，最直接的方法就是从右向左
		int index=nums.length-1;
		while (i<=j ) {
			if (nums[i]*nums[i] > nums[j]*nums[j]){
				result[index--] = nums[i]*nums[i];
				i++;
			}else {
				result[index--] = nums[j]*nums[j];
				j--;
			}
		}


//		System.out.println(Arrays.toString(result));
		return result;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
